package com.atguigu.algorithm.sort;

import java.util.Arrays;

/**
 * 希尔排序
 * 针对插入排序的优化，本质还是插入排序
 *
 * @author xr-8
 * @date 2022-09-11
 * @time 17:00
 */
public class ShellSort {

    public static void main(String[] args) {
        int arr[] = {5, 0, 7, 4, 10, 1};
//        int arr[] = {1, 2, 3, 4, 5, 6};
//        int arr[] = {2, 1, 3, 4, 5, 6};
        sortMove(arr);
//        sortExchange(arr);
    }

    /**
     * 移位法
     * 移位复制直接插入排序的代码
     * @param arr
     */
    public static void sortMove(int[] arr) {
        int insertVal = 0;
        int insertIndex = 0;
        // 增量gap, 并逐步的缩小增量
        for (int gap = arr.length/2; gap > 0 ; gap/=2) {
            // 从第gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                insertVal = arr[i];
                insertIndex = i - gap;
                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                // 当退出while循环时，说明插入的位置找到, insertIndex + 1
                if (insertIndex + gap != i) {
                    arr[insertIndex + gap] = insertVal;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 交换法，效率比移位法低
     * @param arr
     */
    public static void sortExchange(int[] arr) {
        int temp;
        // 增量gap, 并逐步的缩小增量
        for (int gap = arr.length/2; gap > 0 ; gap/=2) {
            // 从第gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (arr[i] < arr[j]) {
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
